public class TestKMP {
    /**
     *
     * @param str 主串
     * @param sub 子串
     * @param pos 从 pos位置开始匹配
     * @return 找到子串在主串中的下标
     */
    public static int KMP (String str,String sub,int pos) {
        if (str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr == 0 || lenSub == 0) return -1;
        if (pos < 0 || pos >= lenStr) return -1;

        int[] next = new int[lenSub];
        getNext(next,sub);

        int i = pos;// 遍历主串
        int j = 0;// 遍历子串
        while (i < lenStr && j < lenSub) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if (j >= lenSub) {
            return i - j;
        }
        return -1;
    }
    public static void getNext(int[] next, String sub) {
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        // 遍历子串
        for (; i < sub.length();) {
            if (k == -1 || sub.charAt(k) == sub.charAt(i-1)) {
                next[i] = k + 1;
                k++;
                i++;
            }else {
                k = next[k];
            }
        }
    }
    public static void main1(String[] args) {

        System.out.println(KMP("ababcabcdabcde", "abcd", 0));
        System.out.println(KMP("ababcabcdabcde", "abcdf", 0));
        System.out.println(KMP("ababcabcdabcde", "ab", 0));
    }


    public static void main(String[] args) {
        repeatedSubstringPattern("abcabcabc");
    }
    public static boolean repeatedSubstringPattern(String s) {
        if(s.length() == 1) return true;
        int len = s.length();
        int[] next = new int[s.length()+1];
        getNext2(next,s+" ");
        if(next[len] > 0 && len % (len-next[len]) == 0) {
            return true;
        }
        return false;
    }
    public static void getNext2(int[] next, String s) {
        next[0] = -1;
        next[1] = 0;

        int k = 0;// 前一个的next值
        int i = 2;// 遍历串
        while(i < s.length()) {
            if(k == -1 || s.charAt(i-1) == s.charAt(k)) {
                next[i] = k + 1;
                i++;
                k++;
            }else {
                k = next[k];
            }
        }
    }
}
